package com.sfx.算法专题.排序.quicksort;

import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-09-04
 * Time: 9:07
 */
public class Code_2_findKthLargest {

    class Solution {
        /**
         * 核心思路 : 也是基于快速排序,把数组划分为三块
         * < key  =key   >key
         * a个    b个    c个
         * [l,left][left+1,right-1][right,r]
         * 由于本题找到的是第k大的,我们进行分类
         * 1): 如果 c>=k ,那么第k大的元素肯定在[right,r]区间内部,
         * 因为c个元素都是数组中最大的一部分,所以第k大的元素肯定在[right,r]区间内部
         * 2): 如果上面区间不符合,那看看是否b + c >=k
         * 如果是 肯定不是在[right,r]区间内部,因为第一次已经判断完了,所以就是在
         * [left+1,right-1内部,直接返回即可-->因为这时>key的
         * 3): 如果a + b + c >k 那么需要在[l,left] 中寻找 第k-b-c
         * 这里千万要记住要把右边去掉的大区间的元素个数排除
         */
        private Random rand = new Random();

        public int quickSort(int[] nums, int l, int r, int k) {
            if (l >= r) return nums[l];
            int left = l - 1, right = r + 1, i = l;
            // 进行数组分三块快排划分-paratition
            int key = nums[rand.nextInt(r - l + 1) + l];
            while (i < right) {
                if (nums[i] < key) {
                    swap(nums, ++left, i++);
                } else if (nums[i] > key) {
                    swap(nums, --right, i);
                } else {
                    i++;
                }
            }
            // right-1 - left -1
            //[l,left][left+1,right-1][right,r];
            int b = right - left - 1;
            int c = r - right + 1;
            if (c >= k) {
                return quickSort(nums, right, r, k);
            } else if (b + c >= k) {
                return key;
            } else {
                return quickSort(nums, l, left, k - b - c);
            }
        }

        private void swap(int[] nums, int left, int right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }

        public int findKthLargest(int[] nums, int k) {
            int topK = quickSort(nums, 0, nums.length - 1, k);
            return topK;
        }
    }
}